package Ep07_BackTrack.Back2_0077;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Jimmy Zhan WORKSTATION
 * @date 2023/7/10 11:50
 * 说明：
 *
 *      k = 2, 两个for循环搞定
 *      k = 3, 三个for循环
 *      因此for循环的嵌套层数是不固定的，所以我们不能用for循环写出固定的泛化代码
 *      不固定层数的for循环，我们使用递归+终止条件来控制即可
 *
 *      递归一次加一个数，return一次就回溯
 */

public class Mine {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtrack(n, k, 1);
        return res;
    }

    private void backtrack(int n, int k, int start){
        // 终止条件
        if (list.size() == k) {
            res.add(new ArrayList<>(list));     // 因为是引用地址，所以会发生改变，要new一个新的
            return;
        }
        // for (int i = start; i <= n; ++i) {
        // 剪枝
        // list中有  list.size() 个元素
        // 剩余要搜索的有 k-list.size()
        // 那么搜索到 n - (k-list.size()) + 1 处即可
        for (int i = start; i <= n - (k-list.size()) + 1; ++i) {
            list.add(i);
            // backtrack(n, k, strat + 1);
            // 这样是错误的，因为每次都会回到start==1的位置，当for中的i++了之后，再传start+1就会导致出现[2,2],[3,2]这种情况
            backtrack(n, k, i + 1);
            // start局部变量各个栈帧都私有一个，return的时候会随栈帧一起弹出，自动回溯
            list.remove(list.size()-1);
        }
    }
}
